package num143;

/**
 * @author : DuJiabao
 * @Date : 2021/1/27 15:12
 * @Project : sword-finger-offer
 * @File : null.java
 * @Desc :给定一个单链表L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
 * https://leetcode-cn.com/problems/reorder-list/
 * 解法： 先找到中点，再将中点后面的链表反转。最后按序穿插组成一个新的链表
 */
class Solution {
  public void reorderList(ListNode head) {
    if (head == null) return;  // 若空，则无需处理
    ListNode midNode = findMiddleNode(head);  // 寻找中点。值得注意的是，当是偶数个结点的时候，返回第N/2个。当奇数个的时候，返回最中间的那个。
    ListNode head2 = midNode.next;  // 中点以后的链表需要被反转
    midNode.next = null;  // 断掉联系，以防万一
    head2 = reverseList(head2);  // 反转
    mergeList(head, head2); // 合并
  }

  /**
   * 寻找链表的中点
   *
   * @param head
   * @return
   */
  private ListNode findMiddleNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    // 这种方法，找到的中点，都是靠左的，要记住
    while (fast.next != null && fast.next.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }
    return slow;
  }

  private ListNode reverseList(ListNode head) {
    ListNode prev = null;  // 无需找回头节点的方法，都无需增加一个伪头节点
    ListNode curr = head;
    while (curr != null) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }

  private void mergeList(ListNode head1, ListNode head2) {
    while (head1 != null && head2 != null) {
      ListNode next1 = head1.next;
      ListNode next2 = head2.next;
//            很巧妙的方法，要记住，可实现两个链表中的两个结点的相互连接
      head1.next = head2;
      head1 = next1;

      head2.next = head1;
      head2 = next2;
    }
  }
}